package com.dycong.common.leetcode.yi;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yilin
 * Date: 2019-09-05
 * Time: 13:01
 * <p>
 * 什么是 Top K 问题？简单来说就是在一堆数据里面找到前 K 大（当然也可以是前 K 小）的数。
 */
public class TopK {

    public static void main(String[] args) {
        solutionByHeap(new int[]{3, 9, 2, 8, 7, 5, 10}, 3).stream().forEach(integer -> System.out.println(integer));
    }

    public static List<Integer> solutionByHeap(int[] input, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k);
        List<Integer> list = new ArrayList<>();
        for (int num : input) {
            if (priorityQueue.size() > 0) {
                System.out.println(priorityQueue.peek());
            }
            if (priorityQueue.size() < k) {
                priorityQueue.add(num);
            } else if (priorityQueue.peek() < num) {
                priorityQueue.poll();
                priorityQueue.add(num);

            }
        }
        while (k-- > 0) {
            list.add(priorityQueue.poll());
        }
        return list;
    }
}
